λ¬Έμ
Programmers - λ§€μΆ νλ½ μ΅μν
π Logic
private static void traversal(int node) {
// ν΄λΉ μ§μμ΄ μν¬μμ μ°Έμ¬νμ§ μλ κ²½μ°
costs[node][0] = 0;
// ν΄λΉ μ§μμ΄ μν¬μμ μ°Έμ¬ν κ²½μ° -> ν΄λΉ μ§μ λ§€μΆμ μ μ₯
costs[node][1] = sales[node];
// 리ν λ
ΈλλΌλ©΄, μμλ‘ μ΅μ λΉμ©μ μ λ¬ν΄μΌ ν¨
if (adjList.get(node).isEmpty()) return;
int extraCost = 10001;
for (int child : adjList.get(node)) {
traversal(child);
// μ΅μ λΉμ©μ λΆλͺ¨ λ
Έλ(νμ₯)μ λμ
if (costs[child][0] < costs[child][1]) {
costs[node][0] += costs[child][0];
costs[node][1] += costs[child][0];
// νμ₯κ³Ό νμ λͺ¨λ μ°Έμ¬νμ§ μμΌλ©΄ μλκΈ°μ νμν μΆκ° λΉμ© κ³μ°
extraCost = Math.min(extraCost, costs[child][1] - costs[child][0]);
} else {
costs[node][0] += costs[child][1];
costs[node][1] += costs[child][1];
// λ μ€ ν λͺ
μ΄λΌλ μ°Έμ¬νλ€λ©΄ μΆκ° λΉμ©μ νμ μμ
extraCost = 0;
}
}
costs[node][0] += extraCost;
}
- ν΄λΉ μ§μμ΄ μν¬μμ μ°Έμ¬ν κ²½μ°μ νμ§ μμ κ²½μ°μ λν λΉμ©μ κ³μ°νλ€.
-
λΆλͺ¨ λ Έλμμλ μμ λ Έλμ λΉμ© μ 보λ₯Ό μ΄μ©ν΄ κ²½μ°μ λ°λ₯Έ λΉμ©μ κ³μ°νλ€.
- μ΄λ, νμ₯κ³Ό νμ λͺ¨λ μ°Έμ¬νμ§ μλ κ²½μ°μ λν μΆκ° λΉμ©μ κ³μ°νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
// μ§μλ³ μν¬μμ μ°Έμ¬νμ λμ λ§€μΆκ³Ό μ°Έμ¬νμ§ μμμ λμ λ§€μΆ, 0: μ°Έμ¬ X, 1: μ°Έμ¬ O
static int[][] costs;
static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
static int[] sales;
public int solution(int[] sales, int[][] links) {
this.sales = sales;
init();
makeAdjList(links);
traversal(0);
return Math.min(costs[0][0], costs[0][1]);
}
private static void init() {
costs = new int[sales.length][2];
for (int i = 0; i < sales.length; i++)
adjList.add(new ArrayList<>());
}
private static void makeAdjList(int[][] links) {
for (int[] link : links)
adjList.get(link[0] - 1).add(link[1] - 1);
}
private static void traversal(int node) {
// ν΄λΉ μ§μμ΄ μν¬μμ μ°Έμ¬νμ§ μλ κ²½μ°
costs[node][0] = 0;
// ν΄λΉ μ§μμ΄ μν¬μμ μ°Έμ¬ν κ²½μ° -> ν΄λΉ μ§μ λ§€μΆμ μ μ₯
costs[node][1] = sales[node];
// 리ν λ
ΈλλΌλ©΄, μμλ‘ μ΅μ λΉμ©μ μ λ¬ν΄μΌ ν¨
if (adjList.get(node).isEmpty()) return;
int extraCost = 10001;
for (int child : adjList.get(node)) {
traversal(child);
// μ΅μ λΉμ©μ λΆλͺ¨ λ
Έλ(νμ₯)μ λμ
if (costs[child][0] < costs[child][1]) {
costs[node][0] += costs[child][0];
costs[node][1] += costs[child][0];
// νμ₯κ³Ό νμ λͺ¨λ μ°Έμ¬νμ§ μμΌλ©΄ μλκΈ°μ νμν μΆκ° λΉμ© κ³μ°
extraCost = Math.min(extraCost, costs[child][1] - costs[child][0]);
} else {
costs[node][0] += costs[child][1];
costs[node][1] += costs[child][1];
// λ μ€ ν λͺ
μ΄λΌλ μ°Έμ¬νλ€λ©΄ μΆκ° λΉμ©μ νμ μμ
extraCost = 0;
}
}
costs[node][0] += extraCost;
}
}
βοΈ Review
- μ κ·Όλ²μ λͺ°λΌ ν€λ§€λ€κ°, νμ΄ μμμ μ°Έκ³ νλ€. νμ΄ μμμ 보λ μ΄μ μλ λΉμ·ν λ¬Έμ λ₯Ό νμλ κ² κ°λ€. (μμ λ Έλμ μ 보λ₯Ό μμλ‘ λ겨주면μ μ΅μ λΉμ©μ ꡬνλ ...?)